package com.major.dawn.leetCode.string;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.List;

public class GroupAnagrams {
    /**
     * 这解法的时间复杂度太高了
     * 并归分组的时间复杂度（n*(n-1)）* 2M
     * 如果是先排序，把它包装成key实现
     * 第一次排序  M*(M-1)*N +n
     *
     * @param strs
     * @return
     */
    public List<List<String>> groupAnagrams(String[] strs) {
        int length = strs.length;
        if (length == 0) {
            return null;
        }
        int[] markIndex = new int[length];
        ArrayList<List<String>> list = new ArrayList<>();

        for (int i = 0; i < length; i++) {

            if (markIndex[i] == 0) {
                ArrayList<String> curList = new ArrayList<>();
                list.add(curList);
                curList.add(strs[i]);

                for (int j = i + 1; j < length; j++) {
                    if (markIndex[j] == 0) {
                        if (isAnagrams(strs[i], strs[j])) {
                            curList.add(strs[j]);
                            markIndex[j] = 1;
                        }
                    }
                }

                markIndex[i] = 1;
            }
        }

        return list;
    }

    private boolean isAnagrams(String str, String s) {
        if (s == null || str == null) {
            return false;
        }
        if (str.equals("") && s.equals("")) {
            return true;
        }
        int strLength = str.length();
        if (s.length() != strLength) {
            return false;
        }
        char[] strChars = str.toCharArray();
        int[] charTable = new int[128];
        for (int i = 0; i < strLength; i++) {
            char strChar = strChars[i];
            charTable[strChar]++;
        }
        char[] sChars = s.toCharArray();
        for (int i = 0; i < strLength; i++) {
            char sChar = sChars[i];
            charTable[sChar]--;
            if (charTable[sChar] < 0) {
                return false;
            }
        }

        return true;
    }


    public List<List<String>> groupAnagramsBySort(String[] strs) {
        HashMap<String, List<String>> stringListHashMap = new HashMap<>();
        for (int i = 0; i < strs.length; i++) {

            String sortChars = sortChars(strs[i]);
//            冒泡排序
            List<String> stringList = stringListHashMap.get(sortChars);
            if (stringList == null) {
                stringList = new ArrayList<>();
                stringListHashMap.put(sortChars, stringList);
            }
            stringList.add(strs[i]);

        }

        Collection<List<String>> values = stringListHashMap.values();
        return new ArrayList<>(values);
    }

    public String sortChars(String str) {
        char[] chars = str.toCharArray();
//        冒泡排序
        for (int j = chars.length; j > 0; j--) {

            for (int i = 0; i < j - 1; i++) {
                if (chars[i] > chars[i + 1]) {
                    char transfer = chars[i];
                    chars[i] = chars[i + 1];
                    chars[i + 1] = transfer;
                }
            }
        }

        return String.copyValueOf(chars);
    }


    public static void main(String[] args) {
        GroupAnagrams groupAnagrams = new GroupAnagrams();
        String[] strings = new String[]{"eat", "tea", "tan", "ate", "nat", "bat"};
        List<List<String>> lists = groupAnagrams.groupAnagrams(strings);
        System.out.println(lists);

        List<List<String>> lists1 = groupAnagrams.groupAnagramsBySort(strings);
        System.out.println(lists1);


        String eat = groupAnagrams.sortChars("eat");
        System.out.println(eat);

    }
}
